#!/usr/bin/python3
"""
   背景题目： 一个含n个元素的整数数组， 处理后的数组变为奇数在前， 偶数在后。
   要求： 空间复杂度为常数， 时间复杂度为O(n)
"""

def is_odd(num):
    """ return true 如果数字num是奇数  """
    return num % 2 != 0

def swap(array, indexA, indexB):
    tmp = array[indexA]
    array[indexA] = array[indexB]
    array[indexB] = tmp

def split_odd_even(num_array):
    "当前位置偶数位置"
    even_index = -1
    current_index = 0
    array_len = len(num_array)
    while(current_index < array_len):
        if is_odd(num_array[current_index]):
            "当前是奇数, 如果前面有偶数, 则置换"
            if even_index != -1:
                swap(num_array, even_index, current_index)
                even_index += 1
        else:
            if even_index == -1:
                even_index = current_index
                
        current_index += 1

if __name__ == '__main__':
    num_array = [1, 2, 3, 4, 333,33,33,5,6,7,4,3,5,2,5, 6, 7, 8, 78, 32, 22, 43, 45, 67]
    print(num_array)
    split_odd_even(num_array)
    print("After split_odd_even:")
    print(num_array)
